package top.hkyzf.study.leetcode.array;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * description: 
 * @author zhufeng
 * @date 2024/3/19 0019 9:02
 * @version V1.0
 */
public class 好子数组的最大分数_1793 {
    /**
     * 超时
     * @param nums
     * @param k
     * @return
     */
    public int maximumScoreBak(int[] nums, int k) {
        int max = 0;
        for (int i = 0; i <= k; i++) {
            for (int j = k; j < nums.length; j++) {
                max = Math.max(calcScore(nums, i, j), max);
            }
        }
        return max;
    }

    private int calcScore(int[] nums, int left, int right) {
        int min = Integer.MAX_VALUE;
        for (int i = left; i <= right; i++) {
            min = Math.min(nums[i], min);
        }
        return min * (right - left + 1);
    }

    /**
     * 官方题解
     * @param nums
     * @param k
     * @return
     */
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;
        int left = k - 1, right = k + 1;
        int ans = 0;
        for (int i = nums[k];; --i) {
            while (left >= 0 && nums[left] >= i) {
                --left;
            }
            while (right < n && nums[right] >= i) {
                ++right;
            }
            ans = Math.max(ans, (right - left - 1) * i);
            if (left == -1 && right == n) {
                break;
            }
        }
        return ans;
    }

    @Test
    public void testMaximumScore () {
        int[] nums = {1,4,3,7,4,5};
        int k =3;
        System.out.println(maximumScore(nums, k));
    }
}
